<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    // 先建立一棵树
    function node(obj) {
        var newobj = {};
        if (obj.length == 1) {
            newobj.value = obj[0];
        } else if (obj.length == 0) {
            newobj.value == null;
        } else {
            newobj.left = node(obj[0]);
            newobj.value = obj[1];
            newobj.right = node(obj[2]);
        }
        return newobj;
    }

    var root = node([[[[7], 11, [2]], 4, []], 5, [[13], 8, [[], 4, [1]]]])
    console.log(root);
    // 中序遍历
    function goTree1(tree) {
        if (tree.hasOwnProperty('left')) {
            goTree1(tree.left);
            console.log(tree.value);
            goTree1(tree.right);
        } else {
            (tree.value == null) ? console.log("") : console.log(tree.value);
        }
    }

    // 前序遍历
    function goTree2(tree) {
        (tree.value == null) ? console.log("") : console.log(tree.value);
        if (tree.hasOwnProperty('left')) {
            goTree2(tree.left);
            goTree2(tree.right);
        }
    }

    // 后序遍历
    function goTree3(tree) {
        if (tree.hasOwnProperty('left')) {
            goTree3(tree.left);
            goTree3(tree.right);
            console.log(tree.value);
        } else {
            (tree.value == null) ? console.log("") : console.log(tree.value);
        }
    }

    //层序遍历
    // 层序遍历需要使用队列的数据结构，这里可以用数组来替代
    // 这里不能使用迭代
    function goTree4(tree) {
        let deque = [];
        deque.push(root);
        while (deque.length != 0) {
            front = deque.shift()
            if (front.hasOwnProperty('left')) {
                deque.push(front.left);
                deque.push(front.right);
            }
            (front.value == null) ? console.log("") : console.log(front.value);
        }
    }


    // 二叉树的深度遍历 dfs
    // 1.先序遍历 根-左-右
    var result = [];
    var dfs = function (node) {
        if (!node) return;
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    // 2.中序遍历 左-根-右
    var result = [];
    var dfs = function (node) {
        if (!node) return;
        dfs(node.left);
        result.push(node.val);
        dfs(node.right);
    }
    // 3.后序遍历 左-右-根
    var result = [];
    var dfs = function (node) {
        if (!node) return;
        dfs(node.left);
        dfs(node.right);
        result.push(node.val);
    }

    // 二叉树的广度遍历 bfs
    // 层序遍历
    var bfs = function (root) {
        var res = [];
        var arr = [root];
        while (arr.length) {
            let temp = [];
            for (let node of arr) {
                res.push(node.val);
                node.left && temp.push(node.left);
                node.right && temp.push(node.right);
            }
            arr = temp;
        }
        return res;
    }
</script>

</html>